232. 用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/description/


typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}Stack;

void StackInit(Stack* ps);

void StackPush(Stack* ps, STDataType data);

STDataType StackTop(Stack* ps);

void StackPop(Stack* ps);

int StackSize(Stack* ps);

void StackDestroy(Stack* ps);

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;

}

bool IsEmpty(Stack* ps)
{
	return  ps->top==0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));
		if (tmp != NULL)
		{
			ps->a = tmp;
		}
		ps->capacity = newcapacity;

	}
	ps->a[ps->top] = data;
	ps->top++;

}


void StackPop(Stack* ps)
{
	assert(ps);
	assert(!IsEmpty(ps));

	ps->top--;

}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!IsEmpty(ps));

	return ps->a[ps->top - 1];
}


int StackSize(Stack* ps)
{
	assert(ps);
	if (IsEmpty(ps))
	{
		return 0;
	}
	return ps->top - 1;

}


void StackDestroy(Stack* ps)
{
	assert(ps);
	
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;

}



typedef struct {
    Stack pushst;
    Stack popst;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("malloc fail\n");
        return NULL;
    }
    StackInit(&obj->pushst);
    StackInit(&obj->popst);

    return obj;
}

void myQueuePush(MyQueue* obj, int x) 
{
    assert(obj);
    StackPush(&obj->pushst,x);

}

int myQueuePeek(MyQueue* obj) 
{
    assert(obj);
    if(IsEmpty(&obj->popst))
    {
        while(!IsEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);
}


int myQueuePop(MyQueue* obj) 
{
    assert(obj);
    int first=myQueuePeek(obj);
    StackPop(&obj->popst);
    return first;
}



bool myQueueEmpty(MyQueue* obj) 
{
    assert(obj);
    return IsEmpty(&obj->pushst)&&
    IsEmpty(&obj->popst);

}

void myQueueFree(MyQueue* obj) 
{
	StackDestroy(&obj->pushst);
	StackDestroy(&obj->popst);
  free(obj);

}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/